#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def fastPower(self, a, module, expo):
        if module == 1:
            return 0

        self.base_remain = a % module
        self.module = module
        return self.power_rec(expo)

    def power_rec(self, expo):
        if expo == 0:
            return 1

        if expo == 1:
            return self.base_remain

        # if expo % 2 == 0:
        divide, residual = expo // 2, expo % 2

        half = self.power_rec(divide)
        half = (half * half) % self.module

        if residual == 0:
            return half
        if residual == 1:
            return (half * self.base_remain) % self.module


def main():
    print("start main")
    s = Solution()
    ret = s.fastPower(3, 1, 0)
    print(ret)

if __name__ == "__main__":
    main()
